package com.company.test;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author zhangyan
 * @version $ Id: SumDemo.java, v 0.1 2020/8/24 17:33 zhangyan Exp $
 */
public class SubSet {


    public static void main(String[] args) {
        SubSet test = new SubSet();
        int[] A = {5, 4, 6};

        test.getSubSet(A, 10, 0);
    }


    public ArrayList<Integer> list = new ArrayList<Integer>();   //用于存放求取子集中的元素

    //求取数组链表中元素和
    public int getSum(ArrayList<Integer> list) {
        int sum = 0;
        for (int i = 0; i < list.size(); i++)
            sum += list.get(i);
        return sum;
    }

    /*
     * 参数step：选中数组A中第step个元素为子集元素
     * 函数功能：求取数组A中一个子集元素，其相加之和等于m
     */
    public void getSubSet(int[] A, int sum, int step) {
        while (step < A.length) {
            list.add(A[step]);   //递归执行语句，向数组链表中添加一个元素
            if (getSum(list) == sum) {  //链表中元素和等于sum
                System.out.println(list);
            }
            step++;
            getSubSet1(A, sum, step);
            list.remove(list.size() - 1);   //回溯执行语句，删除数组链表最后一个元素
        }
    }

    public void getSubSet1(int[] A, int sum, int step) {
        while (step < A.length) {
            list.add(A[step]);   //递归执行语句，向数组链表中添加一个元素
            if (getSum(list) == sum) {  //链表中元素和等于sum
                System.out.println(list);
            }
            step++;
            System.out.println("执行了" + step);
            getSubSet2(A, sum, step);
            list.remove(list.size() - 1);   //回溯执行语句，删除数组链表最后一个元素
        }
    }

    public void getSubSet2(int[] A, int sum, int step) {
        while (step < A.length) {
            list.add(A[step]);   //递归执行语句，向数组链表中添加一个元素
            if (getSum(list) == sum) {  //链表中元素和等于sum
                System.out.println(list);
            }
            step++;
            System.out.println("执行了" + step);
            getSubSet3(A, sum, step);
            list.remove(list.size() - 1);   //回溯执行语句，删除数组链表最后一个元素
        }
    }

    public void getSubSet3(int[] A, int sum, int step) {
        while (step < A.length) {
            list.add(A[step]);   //递归执行语句，向数组链表中添加一个元素
            if (getSum(list) == sum) {  //链表中元素和等于sum
                System.out.println(list);
            }
            step++;
            System.out.println("执行了" + step);
            getSubSet4(A, sum, step);
            list.remove(list.size() - 1);   //回溯执行语句，删除数组链表最后一个元素
        }
    }

    public void getSubSet4(int[] A, int sum, int step) {
        while (step < A.length) {
            list.add(A[step]);   //递归执行语句，向数组链表中添加一个元素
            if (getSum(list) == sum) {  //链表中元素和等于sum
                System.out.println(list);
            }
            step++;
            System.out.println("执行了" + step);
            getSubSet5(A, sum, step);
            list.remove(list.size() - 1);   //回溯执行语句，删除数组链表最后一个元素
        }
    }

    public void getSubSet5(int[] A, int sum, int step) {
        while (step < A.length) {
            list.add(A[step]);   //递归执行语句，向数组链表中添加一个元素
            if (getSum(list) == sum) {  //链表中元素和等于sum
                System.out.println(list);
            }
            step++;
            System.out.println("执行了" + step);
            getSubSet6(A, sum, step);
            list.remove(list.size() - 1);   //回溯执行语句，删除数组链表最后一个元素
        }
    }

    public void getSubSet6(int[] A, int sum, int step) {
        while (step < A.length) {
            list.add(A[step]);   //递归执行语句，向数组链表中添加一个元素
            if (getSum(list) == sum) {  //链表中元素和等于sum
                System.out.println(list);
            }
            step++;
            System.out.println("执行了" + step);
            getSubSet7(A, sum, step);
            list.remove(list.size() - 1);   //回溯执行语句，删除数组链表最后一个元素
        }
    }

    public void getSubSet7(int[] A, int sum, int step) {
        while (step < A.length) {
            list.add(A[step]);   //递归执行语句，向数组链表中添加一个元素
            if (getSum(list) == sum) {  //链表中元素和等于sum
                System.out.println(list);
            }
            step++;
            System.out.println("执行了" + step);
            getSubSet8(A, sum, step);
            list.remove(list.size() - 1);   //回溯执行语句，删除数组链表最后一个元素
        }
    }

    public void getSubSet8(int[] A, int sum, int step) {
        while (step < A.length) {
            list.add(A[step]);   //递归执行语句，向数组链表中添加一个元素
            if (getSum(list) == sum) {  //链表中元素和等于sum
                System.out.println(list);
            }
            step++;
            System.out.println("执行了" + step);
            getSubSet9(A, sum, step);
            list.remove(list.size() - 1);   //回溯执行语句，删除数组链表最后一个元素
        }
    }

    public void getSubSet9(int[] A, int sum, int step) {
        while (step < A.length) {
            list.add(A[step]);   //递归执行语句，向数组链表中添加一个元素
            if (getSum(list) == sum) {  //链表中元素和等于sum
                System.out.println(list);
            }
            step++;
            System.out.println("执行了" + step);
            getSubSet10(A, sum, step);
            list.remove(list.size() - 1);   //回溯执行语句，删除数组链表最后一个元素
        }
    }

    public void getSubSet10(int[] A, int sum, int step) {
        while (step < A.length) {
            list.add(A[step]);   //递归执行语句，向数组链表中添加一个元素
            if (getSum(list) == sum) {  //链表中元素和等于sum
                System.out.println(list);
            }
            step++;
            System.out.println("执行了" + step);
            getSubSet11(A, sum, step);
            list.remove(list.size() - 1);   //回溯执行语句，删除数组链表最后一个元素
        }
    }

    public void getSubSet11(int[] A, int sum, int step) {
        while (step < A.length) {
            list.add(A[step]);   //递归执行语句，向数组链表中添加一个元素
            if (getSum(list) == sum) {  //链表中元素和等于sum
                System.out.println(list);
            }
            step++;
            System.out.println("执行了" + step);
            getSubSet12(A, sum, step);
            list.remove(list.size() - 1);   //回溯执行语句，删除数组链表最后一个元素
        }
    }

    public void getSubSet12(int[] A, int sum, int step) {
        while (step < A.length) {
            list.add(A[step]);   //递归执行语句，向数组链表中添加一个元素
            if (getSum(list) == sum) {  //链表中元素和等于sum
                System.out.println(list);
            }
            step++;
            System.out.println("执行了" + step);
            getSubSet13(A, sum, step);
            list.remove(list.size() - 1);   //回溯执行语句，删除数组链表最后一个元素
        }
    }

    public void getSubSet13(int[] A, int sum, int step) {
        while (step < A.length) {
            list.add(A[step]);   //递归执行语句，向数组链表中添加一个元素
            if (getSum(list) == sum) {  //链表中元素和等于sum
                System.out.println(list);
            }
            step++;
            System.out.println("执行了" + step);
            getSubSet14(A, sum, step);
            list.remove(list.size() - 1);   //回溯执行语句，删除数组链表最后一个元素
        }
    }

    public void getSubSet14(int[] A, int sum, int step) {
        while (step < A.length) {
            list.add(A[step]);   //递归执行语句，向数组链表中添加一个元素
            if (getSum(list) == sum) {  //链表中元素和等于sum
                System.out.println(list);
            }
            step++;
            System.out.println("执行了" + step);
            getSubSet(A, sum, step);
            list.remove(list.size() - 1);   //回溯执行语句，删除数组链表最后一个元素
        }
    }

    public void demo1() {
        int[] a = {5, 4, 6};
        int sum = 10;
        for (int i = 0; i < a.length; i++) {
            list.add(a[i]);
            if (getSum(list) == sum) {
                System.out.println(list);
            }

        }
    }

}
